"""
# Definition for a QuadTree node.

"""
from typing import List


class Node:
    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight


class Solution:
    def construct(self, grid: List[List[int]]) -> 'Node':

        def dfs(x_start, x_end, y_start, y_end) -> Node:
            if x_end < x_start or y_end < y_start: return None
            x_mid = (x_start + x_end) >> 1
            y_mid = (y_start + y_end) >> 1
            vals = set()
            for x in range(x_start, x_end):
                for y in range(y_start, y_end):
                    vals.add(grid[x][y])
            if len(vals) <= 1:
                return Node(vals.pop(),True,None,None,None,None)
            top_left = dfs(x_start,x_mid,y_start,y_mid)
            top_right = dfs(x_start,x_mid, y_mid,y_end)
            bottom_left = dfs(x_mid, x_end,y_start,y_mid)
            bottom_right = dfs(x_mid,x_end,y_mid,y_end)
            return Node(True,False,top_left,top_right,bottom_left,bottom_right)
        n = len(grid)
        return dfs(0,n,0,n)

if __name__ == '__main__':
    s = Solution()
    r = s.construct([[0,1],[1,0]])
    print(r)

